322. Coin Change (medium)

題目描述：
給定不同面額的硬幣和一個總金額 amount，請你計算出可以湊成該金額所需的最少的硬幣數。如果無法湊成該金額，則返回 -1。

輸入: coins = [1, 2, 5], amount = 11
輸出: 3 
解釋: 11 = 5 + 5 + 1

這題容易誤會成是Greedy題，因為直覺上會選擇儘可能大的硬幣，然而這並不總是能夠給出最優解。例如在某些情況下，選擇更小面額的硬幣可能會帶來更好的結果。

Recursive 解法

每個硬幣可以選擇使用或不使用，這樣可以通過遞迴來計算最小硬幣數。 (記住要使用遞迴，就得設好中止條件，讓recursion 能結束，否則會 stack overflow)

class Solution {
public:
    int dfs(vector<int>& coins, int idx, int amount) {
        if (amount == 0) return 0;
        if (amount < 0 || idx >= coins.size()) return INT_MAX;
        int num = INT_MAX, coin = coins[idx];
        int used = dfs(coins, idx, amount-coin);
        if (used != INT_MAX){
            num = used + 1;
        } 
        num = min(num, dfs(coins, idx+1, amount));
        return num;
    }
    int coinChange(vector<int>& coins, int amount) {
        int res = dfs(coins, 0, amount);
        return res== INT_MAX? -1: res;
    }
};

Top-down DP 解法

用額外陣列記錄之前的結果來避免重複計算。不過單純使用一維的 memo[amount] 來存儲結果可能會出錯，因為不同硬幣組合可能導致不同的硬幣數。我們需要用二維的 memo[idx][amount] 來記錄每個硬幣位置和剩餘金額的最小值

class Solution {
public:
    int dfs(vector<int>& coins, int idx, int amount, vector<vector<int>>& memo) {
        if (amount == 0) return 0;
        if (amount < 0 || idx >= coins.size()) return INT_MAX;
        if (memo[idx][amount]) return memo[idx][amount];
        int num = INT_MAX, coin = coins[idx];
        int used = dfs(coins, idx, amount-coin, memo);
        if (used != INT_MAX){
            num = used + 1;
        } 
        num = min(num, dfs(coins, idx+1, amount, memo));
        return memo[idx][amount] = num;
    }

    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>> memo(coins.size(), vector<int>(amount+1, 0));
        int res = dfs(coins, 0, amount, memo);
        return res== INT_MAX? -1: res;
    }
};

Button-Up DP

dp[i] 表示湊成金額 i 所需的最少硬幣數，用以下公式來推出每個 dp[i]：

dp[i] = min(dp[i - coin]) for coin in coins

這轉移式是代表，如果已經知道如何湊成金額 i - coin，那麼只需要再加上這個硬幣 coin，就能湊成 i

初始化dp:
如果金額為 0，所需的硬幣數為 0，即 dp[0] = 0。
對於其他金額，初始化為一個不可能的最大值（如 INT_MAX），表示還不知道如何湊成該金額。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);  
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

DAG 角度

文章Python-LeetCode 581 第14招 Dynamic Programming I： 基本原理與一維DP 提及

「每一個 DP 背後都有一個 dag，DP 需要 dag 指引方向，如同視障者需要 dog。」(Dynamic programming, Bottom-up)

將此題視為 DAG 上的最小權重路徑問題，將這個問題的求解過程視為一個狀態轉換圖：

• 節點：每個節點代表某一個金額 i，從 0 到 amount。
• 邊：從節點 i 到節點 i - coin 的邊表示使用了硬幣 coin 來湊成金額 i，並且每條邊的權重是使用的硬幣數（即 +1）。

起點：dp[0] = 0，從金額 0 開始計算。
終點：希望找到最短路徑到達金額 amount 的節點。

每個節點與其他節點通過不同硬幣面額連接，比如金額 i 可以通過硬幣 1, 2, 或 5 連接到 i-1, i-2, i-5。最終，找到從 dp[0] 到 dp[amount] 的最短路徑就是最優解。